/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package Yacc;

import java.util.*;
/**
 *
 * @author AranciaCheng
 */
public class FollowSet {
	// 核心数据
	public Set<String>[] followSet;
	public Set<String>[] firstSet;

	// 辅助数据
	private String EPSILON="\"\"";
	private String[] nonterminal;
	private String[] orderProductionLeft;
	private ArrayList<String>[] orderProductionRight;

	/**
	 * 构造函数
	 * @param first      FirstSet提供的first集合
	 * @param nontml     FirstSet提供的非终结符数组
	 * @param pLeft      FirstSet提供的经处理生产式左边
	 * @param pRight     FirstSet提供的经处理生产式右边
	 */
	public FollowSet(Set<String>[] first,String[] nontml,String[] pLeft,String[] pRight) {
		nonterminal = nontml;              // 非终结符
		firstSet = first;
		followSet = new TreeSet[nonterminal.length];
		for(int i=0;i<followSet.length;i++) followSet[i] = new TreeSet();

		orderProductionRight= new ArrayList[pLeft.length];
		orderProductionLeft = pLeft;       // (不存在或运算)生产式的左边

		int markBegin = 0;                 // 字符串切割起点
		String token = "";                 // 提取的符号
		for(int i=0;i<pLeft.length;i++){     // (不存在或运算)生产式的右边,从字符串中提取成数组
			orderProductionRight[i] = new ArrayList<String>();
			int length = pRight[i].length();
			for(int j=0;j<length;j++){     // 根据开头标记进行区分提取
				if(pRight[i].charAt(j)=='<'){
					markBegin = j;
					while(pRight[i].charAt(++j)!='>');
					token = pRight[i].substring(markBegin, j+1);
					orderProductionRight[i].add(token);
				}else if(pRight[i].charAt(j)=='"'){
					markBegin = j;
					while(pRight[i].charAt(++j)!='"');
					token = pRight[i].substring(markBegin, j+1);
					orderProductionRight[i].add(token);
				}
			}

		}

	}

	/**
	 * 生成follow集合前的初始化操作
	 */
	public void init(){
		//TODO:存疑的开始生产式
		String startSymbol = nonterminal[0];
		int startSymbolIndex = getIndex(startSymbol);

		// 初始化操作
		followSet[startSymbolIndex].add("$");
		for(int i=0;i<nonterminal.length;i++){
			if(i==startSymbolIndex)continue;
			followSet[i].clear();
		}
	}

	/**
	 * 生成follow集合，结果存于followSet数组中
	 */
	public void make(){
		init();

		boolean processFlag = true;

		// 主处理体
		while(processFlag){
			processFlag = false;
			for(int i=0;i<orderProductionLeft.length;i++){
				int stateNum = orderProductionRight[i].size();

				// walk X1X2X3...XN
				for(int j=0;j<stateNum;j++){
					String currentToken = orderProductionRight[i].get(j);
					if(isNonterminal(currentToken)){ // 仅处理非终结符元素
						String next;
						if(j==stateNum-1){ // 最后一个
							next = EPSILON;
							processFlag =copyA2B(followSet[getIndex(orderProductionLeft[i])], followSet[getIndex(currentToken)])|| processFlag;

						}else{  // 非最后一个:分为三类
							next = orderProductionRight[i].get(j+1);
							if(isNonterminal(next)){
								processFlag = copyA2B(firstSet[getIndex(next)], followSet[getIndex(currentToken)])|| processFlag;
								boolean hasEPSILON = false;
								for(String item:firstSet[getIndex(next)]){
									if(item.equals(EPSILON)){
										hasEPSILON = true;
										break;
									}
								}
								if(hasEPSILON) processFlag =
										copyA2B(followSet[getIndex(orderProductionLeft[i])], followSet[getIndex(currentToken)])||  processFlag;
							}else if(next!=EPSILON){
								if(!followSet[getIndex(currentToken)].contains(next)){
									followSet[getIndex(currentToken)].add(next);
									processFlag = true;
								}
							}else processFlag =
									copyA2B(followSet[getIndex(orderProductionLeft[i])], followSet[getIndex(currentToken)])|| processFlag;


						}
					}
				}// end run X1X2X3...XN
			}// end each production
		} // end main process while

	}

	// print
	public void printFollow(){
		System.out.println("\nfollowset中的元素为：");
		int count = 0;
		while(count < nonterminal.length) {
			System.out.print(count+":");
			Iterator<String> it = followSet[count].iterator();
			while(it.hasNext()) {
				System.out.print(it.next() + " ");
			}
			System.out.println();
			count++;
		}
	}

	// tools
	private boolean isNonterminal(String a){  // 判断是否为非终结符
		for(String non:nonterminal){
			if(a.equals(non)) return true;
		}
		return false;
	}

	private int getIndex(String a){          // 获取该字符在非终结符数组中的下标
		for(int i=0;i<nonterminal.length;i++){
			if(nonterminal[i].equals(a)) return i;
		}
		return -1;
	}

	private boolean copyA2B(Set<String> a, Set<String> b){ // 将set A中的元素复制到set B,除去EPSILON
		int originLength = b.size();
		for(String item:a){
			if(!item.equals(EPSILON)){
				b.add(item);
			}
		}
		int nowLength = b.size();

		// 返回:发生改变(true),未发生改变(false)
		return originLength!=nowLength;
	}


	// interface for AnalysisTable
	public String[] getNonTml(){return nonterminal;}
	public String[] getProLeft(){return orderProductionLeft;}
	public ArrayList<String>[] getProRight(){return orderProductionRight;}


}
